
//使用折半查找法查找数组中的元素

/**
    有序数组
*/

#include <iostream>
using namespace std;


int bin_search(int arr[] , int n,int key)
{

    int low = 0,high = n-1,mid;

    while(low<=high)
    {
        mid = (low+high)/2;
        if(arr[mid]==key)
        {
            return mid;
        }
        if(arr[mid]<key) //右边查找
        {
            low = mid+1;
        }
        if(arr[mid]>key) //左边查找
        {
            high = mid-1;
        }
    }
    return -1;
}


//递归实现
int bin_search_cur(int arr[],int low,int high,int key)
{
    int mid;
    if(low>high)
    {
        return -1;
    }else
    {
        mid = (low+high)/2;
        if(key == arr[mid])
        {
            return mid;
        }
        if(key<arr[mid]) //左边
        {
           return bin_search_cur(arr,low,mid-1,key);
        }
        if(key>arr[mid]) //右边
        {
            return bin_search_cur(arr,mid+1,high,key);
        }
    }
}
int main()
{
    int arr[] = {1,2,3,4,5,6,7};
    cout<<"序号："<<bin_search(arr,7,5)<<endl;

    cout<<"递归下标:"<<bin_search_cur(arr,0,7,5)<<endl;
    system("pause");
    return 0;
}
